Data structure Interview # 3 — Common operations on stacks
Note: There are related exercises in the interview book, but the idea is relatively unclear, and there are typesetting mistakes. The author has rewritten the relevant books and his own views for your reference.
Three, the basic operation of stack
3.1 Constructing stacks with arrays
[Note the following points] :
1. Three elements of array based stack: 1) the maximum size of stack maxSize; 2) Current stack capacity = number of elements in current stack = top-1; 3) Dynamic array storage stack element Type* list;
2. Check whether the stack is empty or full for the operation of removing and loading the stack. If empty or full, there should be exception handling or error message.
3. Pay attention to the push operation, top+1 after the push operation; Pop, on the other hand, is top-1 and then out of the stack. Note that top refers to the position next to the last element in the array.
4. Pay attention to copy constructors and assignment functions, especially when assigning, avoid self-assignment, at the same time pay attention to the size of the inconsistent cannot complete assignment operation, to have relevant prompts.
template<typenameType>
class arrStack
{
public:
arrStack(intnSize=100);
~arrStack(a);arrStack(constarrStack& copyStack);
arrStack&operator= (const arrStack& otherStack);
voidinitializeStack(a);void destroyStack(a);
bool isStackEmpty(a);
bool isStackFull(a);
void push(constType& item);
void pop(Type&poppedItem);
private:
int maxSize;
int top;
Type* list;
};
template<typename Type>
arrStack<Type>::arrStack(int nSize=100)
{
if(nSize < 0)
{
nSize = 100;
list = newType[nSize];
top = 0;
maxSize = 100;
}
else
{
list = newType[nSize];
top = 0; maxSize =nSize; }}template<typename Type>
arrStack<Type>::~arrStack()
{
if(! list) {delete[]list; Delete []list;
list = NULL; }}template<typename Type>
arrStack<Type>::arrStack(const arrStack& copyStack)
{
maxSize =copyStack.maxSize;
top = copyStack.top;
list = newType[maxSize]; // Note that you need to customize the size, which is error prone.
for( int i = 0; i <top; i++) { list[i] =copyStack.list[i]; }}template<typename Type>
arrStack<Type>& arrStack<Type>::operator=(constarrStack& otherStack)
{
if(this ==&otherStack)
{
cout <<"can't copy oneSelf!" << endl;
return *this;
}
else
{
if(maxSize ! =otherStack.maxSize) { cout<<"The Size of two stack are not equal!" << endl;
return*this;
}
else
{
maxSize= otherStack.maxSize;
top =otherStack.top;
for( inti = 0; i < top; i++)
{
list[i]= otherStack.list[i];
}//endfor
return*this; }}//end else
}
template<typename Type>
void arrStack<Type>::initializeStack()
{
destroyStack(a); }template<typename Type>
void arrStack<Type>::destroyStack()
{
top = 0;
}
template<typename Type>
bool arrStack<Type>::isStackEmpty()
{
return (top == 0);
}
template<typename Type>
bool arrStack<Type>::isStackFull()
{
return (top ==maxSize);
}
template<typename Type>
void arrStack<Type>::push(const Type& item)
{
if(!isStackFull())
{
list[top] =item;
top++;
}
else
{
cout <<"The Stack was already Full!"<< endl; }}template<typename Type>
void arrStack<Type>::pop(Type& poppedItem)
{
if(!isStackEmpty())
{
top--;
poppedItem =list[top];
}
else
{
cout <<"The Stack was already Empty!"<< endl; }}Copy the code3.2 Construct stacks with linked lists
List construction stack note:
1) Top ==NULL; Since stack space can be allocated dynamically, you can assume that the stack is never full.
2) The Push operation of the stack shall first determine whether the stack is full or not, and then the stack can be pushed. First push, then adjust the top pointer;
3) The Pop operation of the stack should first determine whether the stack is empty. If it is not empty, the stack can be removed. Adjust the top pointer first, then unstack, and delete the original node.
4) Count can be added to determine the number of current nodes.
template<typename Type>
struct nodeType
{
Type info;
nodeType* link;
};
template<typename Type>
class linkedStack
{
public:
linkedStack(a); ~linkedStack(a);linkedStack(constlinkedStack<Type>&);
linkedStack&operator= (const linkedStack<Type>&);
voidinitializeStack(a);void destroyStack(a);
bool isStackEmpty(a)const;
bool isStackFull(a)const;
void push(constType& item);
void pop(Type&poppedItem);
void nodeCount(a);
voidreversePrint(a);// Non-recursive implementation of reverse printing...
private:
nodeType<Type>*top;
int count; // Count the number of nodes
};
template<typename Type>
linkedStack<Type>::linkedStack()
{
count = 0;
top = NULL;
}
template<typename Type>
linkedStack<Type>::~linkedStack()
{
while( top ! =NULL )
{
nodeType<Type>*tempNode = new nodeType<Type>;
tempNode = top;
top =top->link;
deletetempNode;
}//end if
}
template<typename Type>
linkedStack<Type>::linkedStack(constlinkedStack<Type>& copyStack)
{
if(copyStack.top ! =NULL)
{
nodeType<Type>*current;
nodeType<Type>*first;
nodeType<Type>*newNode;
top = newnodeType<Type>;
top->info =copyStack.top->info; // Top cannot be used directly.
top->link =copyStack.top->link;
first =top; // First follow up the current list...
current =copyStack.top->link; //current copy list...
while( current! =NULL)
{
newNode= new nodeType<Type>;
newNode->link= current->link;
newNode->info= current->info;
first->link= newNode;
first =newNode;
current= current->link;
}//end while
count =copyStack.count;
}//end if
else
{
top = NULL;
count = 0; }}template<typename Type>
linkedStack<Type>&linkedStack<Type>::operator= (const linkedStack<Type>&otherStack)
{
//1 avoids self-assignment
if(this ==&otherStack)
{
cout <<"Can't copy oneself!" << endl;
return *this;
}
/ / 2 others
else
{
if(top ! =NULL)
{
destroyStack(a); }if(otherStack.top! =NULL)
{
nodeType<Type>*current;
nodeType<Type>*first;
nodeType<Type>*newNode;
top =new nodeType<Type>;
top->info= otherStack.top->info;
top->link= otherStack.top->link;
first =top; // First follow up the current list...
current= otherStack.top->link; //current copy list...
while(current ! =NULL)
{
newNode= new nodeType<Type>;
newNode->link= current->link;
newNode->info= current->info;
first->link= newNode;
first= newNode;
current= current->link;
}//endwhile
count =otherStack.count;
}//end if
else
{
top =NULL;
count =0;
}
return *this; }}template<typename Type>
void linkedStack<Type>::initializeStack()
{
destroyStack(a); }template<typename Type>
void linkedStack<Type>::destroyStack()
{
count = 0;
top = NULL;
}
template<typename Type>
bool linkedStack<Type>::isStackEmpty(a)const
{
return (count == 0);
}
template<typename Type>
bool linkedStack<Type>::isStackFull(a)const // Space is not fixed, dynamic application!
{
return false;
}
template<typename Type>
void linkedStack<Type>::push(const Type& item)
{
if(!isStackFull())
{
nodeType<Type>*newNode = new nodeType<Type>;
newNode->info= item;
newNode->link= NULL;
if(top == NULL)
{
top = newNode;
}
else
{
newNode->link= top;
top =newNode;
}
count++;
cout <<item << " was pushed!"<< endl; }}template<typename Type>
void linkedStack<Type>::pop(Type& poppedItem)
{
if(!isStackEmpty())
{
nodeType<Type>*temp = new nodeType<Type>;
temp = top;
poppedItem =top->info;
top =top->link;
count--;
cout <<poppedItem << " was popped!" << endl;
deletetemp; }}template<typename Type>
void linkedStack<Type>::nodeCount()
{
cout <<"nodeCount = " << count << endl;
}
// The recursive implementation of the previous section is a non-recursive implementation of reverse list printing.
template<typename Type>
void linkedStack<Type>::reversePrint(a)// Non-recursive implementation of reverse printing...
{
// The comment section can be used as a non-recursive implementation of the list call stack.
// nodeType
*current = new nodeType
;
// current = top;
// while(current ! = NULL)
/ / {
// pop(current->info);
// current =current->link;
/ /}
int poppedItem = 0;
while(!isStackEmpty())
{
pop(poppedItem);
}
Copy the code\