A stack is a last-in-first-out list data structure. That is, the last item inserted in the list would be the first item to be retrieved in the list. The "inverse" of a stack is a queue.
To understand this structure, imagine twenty plates stacked together. The most obvious way to retrieve a plate is to pluck (pop) it off the top; to add a plate you would probably lift (push) it to the top. By doing otherwise you would risk making several plates fall to the floor and shatter. (This metaphor is based on the Tower of Hanoi, a common puzzle game.)
Common operations are:
- push - adds an item to the top.
- pop - removes and returns the top item.
Less common operations are:
- count - number of items in the stack
- peek - retrieves the next item in the stack without removing it from the stack.
Stack structure[]
A simple stack can be implemented using nodes with the linked list structure.
Creation of a stack[]
A new empty stack without using sentinel nodes:
node* top = null; // where top represents the last item in the stack
Pushing an item[]
newnode is allocation for a new node.
int x;
// assign a value to x
node* new = newnode(x);
if(top==null) {
*top = new;
}
else {
top->next = new;
*top = new;
}
Popping the stack[]
free is deallocation for the node.
int return_value;
if(top==null) {
// stack underflow
}
else {
return_value = top->value;
node* t = top;
top = top->next;
free(t);
}
External links[]
- Stack at Wikipedia