Stacks & Queues
Stack ADT definition:
A stack is a linear sequence of data of the same type. It can be likened to a stack of plates at a diner. The plates are taken off in a "last in, first out" order.
operations of a stack:
they have top and bottom
can put on top and take off top ONLY
key words to remember:
push - to push is to place an item on the top of a stack.
pop - to pop from a stack is to remove an item from the top.
top - refers to the top of the stack.
Pop does not return the value of the top of stack. It just removes it.
Example of Stack class:
class Stack
{
char ar[50]; // type of data in stack
int n; // number of elements in stack
public:
Stack();
void push(char);
void pop();
char top()const;
bool empty()const;
bool full()const;
int size()const;
};
/********************************/
Stack::Stack()
{
n=0; // says no elements in array
}
/********************************/
bool Stack::empty()
{
return (n==0); // evaluates ==0 for true and != 0 for false
}
/********************************/
bool Stack::full()
{
return (n==50); // or use symbolic constant
}
/********************************/
void Stack::push(char c)
{
if(n==50)
return; // stack is full
// insert onto stack
ar[n] = c; // or optional ar[n++] = c
n++;
}
/*********************************/
Stack::pop()
{
if (empty)
return;
n--;
}
Queue: (FIFO or first in first out)
an abstract data type which is a sequence of data of the same typeit has a front and a back.works well for list of things to do like print spoolersarray implementation is for a set size of queue
linked list implementation which are much more efficient
functions of a queue:
push( ) to push a value onto the queue.
pop( ) to pop a value off of the queue.
front( ) similar to top( ) in a stack so you can examine.
In an array implementation of a queue you can push something onto the front of the list and then push another element on. You can keep track of the list size.
Problem with the array implementation is that you can keep track of size but when you pull off the front, you have to move all other values down. This takes time and resources.
Solution is to keep track of the first and last numbers in the queue. As you add in, the back moves. And as you pop things off, the front moves as well. This is still a problem because you eventually run out of room in the queue. Or… an even better solution to this problem is a circular queue. This brings us to yet another new data structure:
deque: (pronounced deck)
a deque is a linear data structure with a sequence of elements. It is a special case of a queue has both a front and a back. It is essentially a double ended queue. The main difference is that you can push and pop off of either the front or back.
Colombo Time
