现在的位置: 首页 > 综合 > 正文

跟我学数据结构：(4) 栈 (Stack)

2013年10月07日 ⁄ 综合 ⁄ 共 4364字 ⁄ 字号 小 中 大 ⁄ 评论关闭

 

跟我学数据结构: （4）栈
摘要：
本文通过实际代码，演示了用C++实现数据实现的固定容量的栈。
读者对象：
   C++有一定基础的同学。
 
栈
栈虽然简单，但在数据结构中非常重要。在计算机算法世界里，很多场合中都是利用栈巧妙解决问题的。
 
设计说明
本文的代码有三部分组成。
1） Stack.h, Stack.cpp
我们用c++封装了栈的实现。
2） Main.cpp
主函数构造了一个Stack_T 对象的实例stack。程序运行后，在界面上要求用户输入名字。系统把用户输入的字符放进栈中。然后在依次出栈，完成了字符串的顺序的反转。
3） Makefile
之前的示例我们都只有一个文件，直接通过 g++ 进行编译。本例特地将一个文件可以实现的代码根据逻辑划分成多个，编写makefile脚本，用gnu make来编译程序。 这样，你可以了解用makefile来管理多个文件组成的项目。
 
代码和运行结果
本文件的代码已提交至svn中。
 
 
stack.h
Code:
  1. //////////////////////////////////////////////////////////////////////////   
  2. // file: stack.h   
  3. // auth: jiangtao <jiangtao@tao-studio.net>   
  4. // date: 2009-6-3   
  5. //   
  6. //////////////////////////////////////////////////////////////////////////   
  7.   
  8. #ifndef stack_h__   
  9. #define stack_h__   
  10.   
  11. // The stack consists of Element_T   
  12. typedef int Element_T;   
  13.   
  14. class Stack_T   
  15. {   
  16. public:   
  17.     // Initialize a new stack so that it is empty.   
  18.     Stack_T (void);   
  19.   
  20.     // Copy constructor   
  21.     Stack_T (const Stack_T& s);   
  22.   
  23.     // Assignment operator   
  24.     Stack_T& operator = (const Stack_T& s);   
  25.   
  26.     //Perform actions when stack is destroyed.   
  27.     ~Stack_T (void);   
  28.   
  29.     // Place a new item on top of the stack   
  30.     // Does not check if the stack is full.   
  31.     void push (Element_T newItem);   
  32.   
  33.     // Remove and return the top stack item   
  34.     // Dose not check if stack is empty.   
  35.     Element_T pop (void);   
  36.   
  37.   
  38.     // Return top stack item without removing it   
  39.     // Does not check if stack is empty.   
  40.     Element_T top (void);   
  41.   
  42.     // Returns 1 if the stack is empty,   
  43.     // otherwise returns 0.   
  44.     int isEmpty (void);   
  45.   
  46.     // Returns 1 if stack full, else returns 0   
  47.     int isFull ( void);   
  48.   
  49. private:   
  50.     // bottom and maximun size of the stack   
  51.     enum    
  52.     {   
  53.        BOTTOM = 0,   
  54.        SIZE  = 100,   
  55.     };   
  56.   
  57.     // Keeps track of the current top of stack.   
  58.     int stackTop_;   
  59.   
  60.     // Holds the stack's contents.   
  61.     Element_T stack_[SIZE];   
  62.   
  63. };   
  64. #endif // stack_h__   
stack.cpp
Code:
  1. //////////////////////////////////////////////////////////////////////////   
  2. // file: stack.cpp   
  3. // auth: jiangtao <jiangtao@tao-studio.net>   
  4. // date: 2009-6-3   
  5. //   
  6. //////////////////////////////////////////////////////////////////////////   
  7.   
  8. #include "stack.h"   
  9.   
  10. Stack_T::Stack_T(void)   
  11. : stackTop_ (Stack_T::BOTTOM)   
  12. {   
  13.     //no-op   
  14. }   
  15.   
  16. Stack_T::Stack_T(const Stack_T& s)   
  17. : stackTop_ (s.stackTop_)   
  18. {   
  19.     for (int i = 0; i < s.stackTop_; i++)   
  20.     {   
  21.         this->stack_[i] = s.stack_[i];   
  22.     }   
  23. }   
  24.   
  25. Stack_T&  Stack_T::operator = (const Stack_T& s)   
  26. {   
  27.     if (this != &s)   
  28.     {   
  29.         this->stackTop_ = s.stackTop_;   
  30.         for (int i = 0; i < s.stackTop_; i++)   
  31.         {   
  32.             this->stack_[i] = s.stack_[i];   
  33.         }   
  34.     }   
  35.     return *this;   
  36. }   
  37.   
  38.   
  39. Stack_T::~Stack_T(void)    
  40. {   
  41.     //    
  42. }   
  43.   
  44. void Stack_T::push(Element_T newItem)   
  45. {   
  46.     this->stack_[this->stackTop_++] = newItem;   
  47. }   
  48.   
  49. Element_T Stack_T::pop(void)   
  50. {   
  51.     return this->stack_[-- this->stackTop_];   
  52. }   
  53.   
  54. Element_T Stack_T::top(void)   
  55. {   
  56.     return this->stack_[this->stackTop_ - 1];   
  57. }   
  58.   
  59. int Stack_T::isEmpty(void)   
  60. {   
  61.     return this->stackTop_ == Stack_T::BOTTOM;   
  62. }   
  63.   
  64. int Stack_T::isFull(void)   
  65. {   
  66.     return this->stackTop_ >= Stack_T::SIZE;   
  67. }   
  68.   
main.cpp
Code:
  1. //////////////////////////////////////////////////////////////////////////   
  2. // file: main   
  3. // auth: jiangtao <jiangtao@tao-studio.net>   
  4. // date: 2009-6-3   
  5. //   
  6. //////////////////////////////////////////////////////////////////////////   
  7. #include "stack.h"   
  8. #include <iostream>   
  9. using namespace std;   
  10.   
  11. int main (int argc, char* argv[])   
  12. {   
  13.     cout << argv[0] << " start here." << endl;   
  14.     const int MAX_NAME_LEN = 64;   
  15.     char name[MAX_NAME_LEN];   
  16.   
  17.     Stack_T stack;   
  18.   
  19.     cout << " Please enter you name. :";   
  20.     cin.getline(name,MAX_NAME_LEN);   
  21.   
  22.     for (int i = 0; name[i] != '/0' && !stack.isFull(); i++)   
  23.     {   
  24.         stack.push(Element_T (name[i]));   
  25.     }   
  26.   
  27.     cout << "/nyour name backwards is ..:";   
  28.     while (!stack.isEmpty())   
  29.     {   
  30.         cout << char (stack.pop());   
  31.     }   
  32.     cout << endl;   
  33.     return 0;   
  34.   
  35. }   
 
makefile
 
Code:
  1. CC=g++   
  2. CFLAGS=-O2 -W    
  3. LIBS=   
  4.   
  5. stack: main.cpp stack.cpp   
  6.     $(CC) $(CFLAGS) -c main.cpp stack.cpp   
  7.     $(CC) main.o stack.o $(LIBS) -o stack   
  8. clean:   
  9.     rm *.o   
 
Code:
  1. 输出结果   
  2.   
  3. ./stack start here.   
  4.  Please enter you name. : jiangtao   
  5. your name backwards is ..:oatgnaij   

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞