合法栈输出队列的充要条件

问题背景

Algorithm 4th (Robert Sedgewick, Kevin Wayne) 一书中有这样一道习题:

1.3.46 Forbidden triple for stack generability. Prove that a permutation can be gener- ated by a stack (as in the previous question) if and only if it has no forbidden triple (a, b, c) such that a < b < c with c first, a second, and b third (possibly with other intervening integers between c and a and between a and b).

翻译成中文,可以理解为:请证明:如果一个栈的出栈顺序合法,当且仅当不存在这样的 forbidden triple:在序列中编号 c 后有编号 a、b,其中 c和a, a和b可以有间隔,而且 a < b < c。 查看全文

单项链表查找、相交或成环的几个算法

这篇文章介绍了单项链表上有关相交和成环的几个问题和算法。

你也可以参考有关单项链表的另外几篇文章:

单项链表实现的栈

反转单项链表的四种算法 查看全文

反转单向链表的四种实现(递归与非递归,C++)

单项链表的反转指的是这样一类问题:给定一个单项链表的头指针 head,写一个算法,将其反转,并返回新的头指针 head'。

本文给出了这一问题的两种解法,分别是递归解法和非递归解法。 查看全文

模板类 Stack C++ 实现(链表版)

使用模板类实现 Stack 类型,内部采用单链表。注意:也可以使用变长数组实现,详见这里

  1. 链表使用嵌入类型(子类型)的一个结构 Node 实现。C++ 中的嵌入类型是语法上的嵌入(这种说法可能不能算十分严谨),所以 Node 理论上和其它的类型并无区别,但是因为其访问属性为 private,就避免了外界接触其实现细节。使用这种实现方式,主要是因为C++不存在直接的私有类
  2. 对于每一个 node,其定义为一个代表项目的 val 和代表下一项的地址的指针 next。
  3. 因为是要实现栈,LIFO (后入先出)的规则,决定了我们只需要存储一个 head 指针,每次的 push 和 pop 只需要针对头部的第一个元素进行就可以了。

下面是代码。

/*
 * A Stack Implement
 * With Linked List
 *
 * Copyright(C) Ceeji Cheng <hi.ceeji@gmail.com>
 */
#include <iostream>
 
#ifndef _STACK_H_
#define _STACK_H_
 
/*
 * stack<T> : a stack implement template class
 */
template<typename T>
class stack {
public:
	stack();
	void push(const T& element); // push an element to this stack
	T pop(); // pop an element from this stack
	T peek(); // get the top element on this stack without poping it
	int size(); // get the size of this stack
	bool isEmpty(); // is the stack empty
 
private:
// a struct to present a linked list node.
struct node {
	const T * val; // the value of this node
	node *next;    // a ptr to the next node
};
 
	node* head;
	int n; // count
};
 
template<typename T>
stack<T>::stack() {
	// init the variable
	this->n = 0;
	this->head = NULL;
}
 
template<typename T>
void stack<T>::push(const T& element) {
	node *oldHead = this->head;
	this->head = new node();
	this->head->val = new T(element);
	this->head->next = oldHead;
	++n;
}
 
template<typename T>
T stack<T>::pop() {
	if (this->isEmpty()) {
		throw "empty stack";
	}
 
	const T *retPtr = this->head->val;
	node *newHead = this->head->next;
	delete this->head;
	this->head = newHead;
 
	--n;
	return *retPtr;
}
 
template<typename T>
T stack<T>::peek() {
	if (this->isEmpty()) {
		throw "empty stack";
	}
 
	const T *retPtr = this->head->val;
	return *retPtr;
}
 
template<typename T>
inline bool stack<T>::isEmpty() {
	return n == 0;
}
 
template<typename T>
inline int stack<T>::size() {
	return n;
}
 
#endif

其实这个类有很多可以扩充的地方,不过栈应该具有的基本功能已经比较完备了。

模板类 Stack C++ 实现(线性存储版)

今天自己写了一个 C++ 中的栈(stack)实现,在实现的时候主要问题如下。

在 C++ 中,容器类是没办法实现“只存储引用”这个目标的。假如我想实现一个只存储引用(也就是存储指针)的容器,那意味着我必须保证引用不悬空(不产生悬空指针)。然而,用户push到栈中的元素可能是局部变量,那么万一用户将我的stack传递到函数体外,就无法保证这一点了。所以,任何容器类必须面临“复制构造函数”的时耗。

使用数组 T* arr = new T[count]; 的时候,每一个arr的成员都将被自动地初始化。由于分配空间是比较耗时的,我们一般会以翻倍的长度提前分配内存空间。然而,我们的内存空间是用来存储push的成员的,不需要初始化新成员。方法就是改变T为T的指针类型。

/*
 * A Stack Implement
 * With Resizing Array
 *
 * Copyright(C) Ceeji Cheng <hi.ceeji@gmail.com>
 */
#include 
 
#ifndef _STACK_H_
#define _STACK_H_
 
/*
 * stack : a stack implement template class
 */
template
class stack {
public:
    stack();
    void push(const T& element); // push an element to this stack
    T pop(); // pop an element from this stack
    int size(); // get the size of this stack
    bool isEmpty(); // is the stack empty
 
private:
    void resizeCapacity(); // resize the capacity of stack
    (const T*)* arr;
    int n; // count
    int capacity; 
};
 
template
stack::stack() {
    // init the variable
    this->n = 0;
    this->capacity = 1; // default capacity is 1
 
    // alloc memory for stack
    arr = new const T*[this->capacity];
}
 
template
void stack::push(const T& element) {
    // check memory size
    if (this->size() == this->capacity) {
        this->capacity = this->capacity << 1; // capacity *= 2
        resizeCapacity();
    }
 
    //push element
    arr[n++] = new T(element); // add the reference
}
 
template
T stack::pop() {
    // get the element
    T tmp(*arr[--n]);
    // release memory
    delete arr[n];
    // resize the capacity
    if (this->capacity / this->size() >= 3) {
        this->capacity = this->size();
        this->resizeCapacity();
    }
 
    return tmp;
}
 
template
inline bool stack::isEmpty() {
    return n == 0;
}
 
template
inline int stack::size() {
    return n;
}
 
/*
 * resize the capacity of this stack
 */
template
void stack::resizeCapacity() {
    const T** tmp = new const T*[this->capacity];
 
    for (int i = 0; i < n; ++i) {
        tmp[i] = this->arr[i];
    }
 
    delete[] this->arr;
 
    this->arr = tmp;
}
#endif
1 3 4 5 6 7 64