本文共 6979 字，大约阅读时间需要 23 分钟。
算法导论原题：
10.1-2 Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n.The PUSH and POP operations should run in O(1) time. 即：用数组 A[1..n] 实现两个栈，只有当它们的数据元素和为n的时候才会上溢。PUSH和POP操作都应该是O(1)。
- 单向栈可以看作只能从左端push，所以这个双向栈可以看作从左右任意一端push，由原来的一个top指向改为两个top指向，一个从左端开始，一个从右端开始。
- 判断栈满，只需要判断左端的top超过右端的top即为栈满。
//BothwayStack.h#pragma once#includetemplate class BothwayStack{public: enum Direction{E_Left,E_Right}; BothwayStack(unsigned int size); bool Push(Direction direction, ElemType elem); bool Pop(Direction direction, ElemType* elem); bool Empty(Direction direction); bool Visit(ElemType* elem, unsigned int pos);private: unsigned int m_size; unsigned int m_leftTop; unsigned int m_rightTop; ElemType* m_array;};template bool BothwayStack ::Visit(ElemType* elem, unsigned int pos){ if (pos >= m_size || pos < 0) { assert(false && "Error: Visit Pos is out range of array!"); return false; } *elem = m_array[pos]; return true;}template bool BothwayStack ::Empty(Direction direction){ if (direction == E_Left) { if(m_leftTop == 0) { return true; } } else if(direction == E_Right) { if (m_rightTop == m_size - 1) { return true; } } return false;}template BothwayStack ::BothwayStack(unsigned int size) :m_array(new ElemType[size]),m_size(size),m_leftTop(0),m_rightTop(size-1){ memset(m_array,0,sizeof(ElemType)*size);}template bool BothwayStack ::Pop(Direction direction, ElemType* elem){ if (Empty(direction)) { return false; } if (direction == E_Left) { *elem = m_array[--m_leftTop]; } else if(direction == E_Right) { *elem = m_array[++m_rightTop]; } return true;}template bool BothwayStack ::Push(Direction direction, ElemType elem){ if (m_leftTop > m_rightTop) //判断双向栈是否已满 { return false; } if (direction == E_Left) { m_array[m_leftTop++] = elem; } else if(direction == E_Right) { m_array[m_rightTop--] = elem; } return true;}
//Util.h#pragma oncenamespace Util{ template void PrintMemory(T& dateStruct, unsigned int size) { cout << "PrintMemory: "; for (int i = 0; i != size; i++) { ElemType tempElem; dateStruct.Visit(&tempElem,i); printf("%d ",tempElem); } printf("\n"); }} //main.cpp#include "Util.h"#include "BothwayStack.h"#includeusing namespace std;typedef int ElemType;int main(){ const int QUEUE_SIZE = 10; BothwayStack testBothwayStack(QUEUE_SIZE); Util::PrintMemory(testBothwayStack,QUEUE_SIZE); cout << "BothwayStack's Left is " << (testBothwayStack.Empty(BothwayStack ::E_Left) ? "Empty." : "Not Empty.") << endl; cout << "BothwayStack's Right is " << (testBothwayStack.Empty(BothwayStack ::E_Right) ? "Empty." : "Not Empty.") << endl; for (int i = 1; i != 8; i++) { testBothwayStack.Push(BothwayStack ::E_Left,i); cout << "\nLeftPush:" << i << endl; Util::PrintMemory(testBothwayStack,QUEUE_SIZE); cout << "BothwayStack's Left is " << (testBothwayStack.Empty(BothwayStack ::E_Left) ? "Empty." : "Not Empty.") << endl; cout << "BothwayStack's Right is " << (testBothwayStack.Empty(BothwayStack ::E_Right) ? "Empty." : "Not Empty.") << endl; } for (int i = 1; i != 4; i++) { testBothwayStack.Push(BothwayStack ::E_Right,i); cout << "\nRightPush:" << i << endl; Util::PrintMemory(testBothwayStack,QUEUE_SIZE); cout << "BothwayStack's Left is " << (testBothwayStack.Empty(BothwayStack ::E_Left) ? "Empty." : "Not Empty.") << endl; cout << "BothwayStack's Right is " << (testBothwayStack.Empty(BothwayStack ::E_Right) ? "Empty." : "Not Empty.") << endl; } for (int i = 1; i != 3; i++) { int tempElem; testBothwayStack.Pop(BothwayStack ::E_Left,&tempElem); cout << "\nLeftPop:" << tempElem << endl; Util::PrintMemory(testBothwayStack,QUEUE_SIZE); cout << "BothwayStack's Left is " << (testBothwayStack.Empty(BothwayStack ::E_Left) ? "Empty." : "Not Empty.") << endl; cout << "BothwayStack's Right is " << (testBothwayStack.Empty(BothwayStack ::E_Right) ? "Empty." : "Not Empty.") << endl; } for (int i = 1; i != 4; i++) { int tempElem; testBothwayStack.Pop(BothwayStack ::E_Right,&tempElem); cout << "\nRightPop:" << tempElem << endl; Util::PrintMemory(testBothwayStack,QUEUE_SIZE); cout << "BothwayStack's Left is " << (testBothwayStack.Empty(BothwayStack ::E_Left) ? "Empty." : "Not Empty.") << endl; cout << "BothwayStack's Right is " << (testBothwayStack.Empty(BothwayStack ::E_Right) ? "Empty." : "Not Empty.") << endl; } return 0;}
PrintMemory: 0 0 0 0 0 0 0 0 0 0
BothwayStack’s Left is Empty. BothwayStack’s Right is Empty.LeftPush:1
PrintMemory: 1 0 0 0 0 0 0 0 0 0 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Empty.LeftPush:2
PrintMemory: 1 2 0 0 0 0 0 0 0 0 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Empty.LeftPush:3
PrintMemory: 1 2 3 0 0 0 0 0 0 0 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Empty.LeftPush:4
PrintMemory: 1 2 3 4 0 0 0 0 0 0 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Empty.LeftPush:5
PrintMemory: 1 2 3 4 5 0 0 0 0 0 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Empty.LeftPush:6
PrintMemory: 1 2 3 4 5 6 0 0 0 0 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Empty.LeftPush:7
PrintMemory: 1 2 3 4 5 6 7 0 0 0 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Empty.RightPush:1
PrintMemory: 1 2 3 4 5 6 7 0 0 1 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Not Empty.RightPush:2
PrintMemory: 1 2 3 4 5 6 7 0 2 1 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Not Empty.RightPush:3
PrintMemory: 1 2 3 4 5 6 7 3 2 1 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Not Empty.LeftPop:7
PrintMemory: 1 2 3 4 5 6 7 3 2 1 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Not Empty.LeftPop:6
PrintMemory: 1 2 3 4 5 6 7 3 2 1 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Not Empty.RightPop:3
PrintMemory: 1 2 3 4 5 6 7 3 2 1 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Not Empty.RightPop:2
PrintMemory: 1 2 3 4 5 6 7 3 2 1 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Not Empty.RightPop:1
PrintMemory: 1 2 3 4 5 6 7 3 2 1 BothwayStack’s Left is Not Empty. BothwayStack’s Right is Empty.
转载地址：http://anyii.baihongyu.com/